package com.leetcode.LeetCode精选TOP面试题;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2022-06-06 16:00
 */
public class 题库_0076_最小覆盖子串 {

  static
  class Solution {
    public String minWindow(String s, String t) {
      if (s == null || s.length() == 0 || t == null || t.length() == 0) {
        return "";
      }
      Map<Character, Integer> maps = new HashMap<>();
      for (char ch : t.toCharArray()) {
        maps.compute(ch, (key, value) -> value == null ? 1 : value + 1);
      }
      int count = t.length();

      int answerLeft = -1;
      int answerRight = s.length();

      int left = 0;
      for (int right = 0; right < s.length(); ++right) {
        char rightKey = s.charAt(right);
        if (maps.containsKey(rightKey)) {
          Integer rightValue = maps.get(rightKey);
          if (rightValue > 0) {
            --count;
          }
          maps.put(rightKey, rightValue - 1);
        }
        // 定位到一个合适的右边界，此时定位一个合适的左边界
        if (count == 0) {
          while (count == 0) {
            char leftKey = s.charAt(left);
            if (maps.containsKey(leftKey)) {
              Integer leftValue = maps.get(leftKey);
              if (leftValue >= 0) {
                ++count;
              }
              maps.put(leftKey, leftValue + 1);
            }
            ++left;
          }

          if (answerRight - answerLeft > ((right + 1) - (left - 1))) {
            answerLeft = left - 1;
            answerRight = right + 1;
          }
        }
      }

      return answerLeft == -1 ? "" : s.substring(answerLeft, answerRight);
    }
  }

}
